import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-03-20
 * Time:13:24
 */
/**
 * 2039. 网络空闲的时刻
 * 给你一个有 n 个服务器的计算机网络，服务器编号为 0 到 n - 1 。
 * 同时给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 
 * 表示服务器 ui 和 vi 之间有一条信息线路，在 一秒 内它们之间可以传输 任意 数目的信息。
 * 再给你一个长度为 n 且下标从 0 开始的整数数组 patience 。
 * 题目保证所有服务器都是 相通 的，也就是说一个信息从任意服务器出发，
 * 都可以通过这些信息线路直接或间接地到达任何其他服务器。
 * 编号为 0 的服务器是 主 服务器，其他服务器为 数据 服务器。
 * 每个数据服务器都要向主服务器发送信息，并等待回复。信息在服务器之间按 最优 线路传输，
 * 也就是说每个信息都会以 最少时间 到达主服务器。
 * 主服务器会处理 所有 新到达的信息并 立即 按照每条信息来时的路线 反方向 发送回复信息。
 * 在 0 秒的开始，所有数据服务器都会发送各自需要处理的信息。从第 1 秒开始，
 * 每 一秒最 开始 时，每个数据服务器都会检查它是否收到了主服务器的回复信息（包括新发出信息的回复信息）：
 * 如果还没收到任何回复信息，那么该服务器会周期性 重发 信息。
 * 数据服务器 i 每 patience[i] 秒都会重发一条信息，也就是说，
 * 数据服务器 i 在上一次发送信息给主服务器后的 patience[i] 秒 后 会重发一条信息给主服务器。
 * 否则，该数据服务器 不会重发 信息。
 * 当没有任何信息在线路上传输或者到达某服务器时，该计算机网络变为 空闲 状态。
 * 请返回计算机网络变为 空闲 状态的 最早秒数 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/the-time-when-the-network-becomes-idle
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
public class TestDemo {
    static int N = 100007, E = N * 2, INF = 0x7f7f7f7f;
    static int[] head = new int[N], edg = new int[E], nxt = new int[E];
    static int[] dist = new int[N];
    static int idx = -1;

    public static void clear() {
        Arrays.fill(head, -1);
        Arrays.fill(dist, INF);
        dist[0] = 0;
        idx = -1;
    }

    public static void add(int u, int v) {
        edg[++idx] = v;
        nxt[idx] = head[u];
        head[u] = idx;
    }

    public static int networkBecomesIdle(int[][] edges, int[] patience) {
        // 建图（链式前向星）
        int n = patience.length;
        clear();
        for (int[] e : edges) {
            add(e[0], e[1]);
            add(e[1], e[0]);
        }

        // 计算最短路
        Deque<Integer> st = new ArrayDeque<>();
        st.addLast(0);
        while (!st.isEmpty()) {
            int cur = st.pollFirst(), d = dist[cur] + 1;
            for (int e = head[cur]; e != -1; e = nxt[e]) {
                int ne = edg[e];
                if (dist[ne] > d) {
                    dist[ne] = d;
                    st.addLast(ne);
                }
            }
        }

        // 计算空闲时间
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            int j = dist[i];
            ans = Math.max(ans, Math.max(2 * j + 1, (2 * j - 1) / patience[i] * patience[i] + 2 * j + 1));
        }
        return ans;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {1, 2}};
        int[] patience = {0, 2, 1};
        System.out.println(networkBecomesIdle(edges,patience));
    }
}
